package leetcode100;

import java.util.ArrayList;
import java.util.HashMap;

public class LRUCache {

    private int capacity;
    private LRUNode head;
    private LRUNode tail;
    private int size;
    private HashMap<Integer,LRUNode> map;

    static class LRUNode {
        int key;
        int value;
        LRUNode pre;
        LRUNode next;

        public LRUNode(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public LRUNode() {
        }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.head = new LRUNode();
        this.tail = new LRUNode();
        this.head.next = this.tail;
        this.tail.pre = this.head;
        this.map = new HashMap<>(capacity);
    }


    public int get(int key) {
        if (!this.map.containsKey(key)) {
            return -1;
        }
        LRUNode node  = this.map.get(key);
        this.remove(node);
        this.addLast(node);
        return this.map.get(key).value;
    }

    public void remove(LRUNode node) {
        LRUNode preNode = node.pre;
        LRUNode nextNode = node.next;
        node.pre=null;node.next=null;
        preNode.next = nextNode;
        nextNode.pre = preNode;

    }

    public void addLast(LRUNode newNode) {
        LRUNode pre = this.tail.pre;
        pre.next = newNode;
        this.tail.pre = newNode;
        newNode.next =this.tail;
        newNode.pre = pre;
    }

    public void put(int key, int value) {

        //已存在key
        if (this.map.containsKey(key)) {
            LRUNode node = map.get(key);
            this.remove(node);
            node.value=value;
            this.addLast(node);
            return;
        }

        //不存在未超出,加在尾部
        LRUNode newNode = new LRUNode(key, value);
        this.map.put(key,newNode);
        if (this.size<this.capacity) {
            this.addLast(newNode);
            this.size++;
            return ;
        }

        //不存在已超出,删头加尾;
        LRUNode removeNode = this.head.next;
        this.remove(removeNode);
        this.map.remove(removeNode.key);
        this.addLast(newNode);
    }
}
